// 员工的重要性：https://leetcode-cn.com/problems/employee-importance/submissions/
package main

import "container/list"

//Definition for Employee.
type Employee struct {
	Id int
	Importance int
	Subordinates []int
}



// 使用BFS 解题， 线性搜索
func getImportance(employees []*Employee, id int) int {
	// 先找到领导
	// 线性搜索遍历
	var boos *Employee
	for _, emp := range employees {
		if emp.Id == id {
			boos = emp
		}
	}
	rst := 0
	d := list.New()
	d.PushBack(boos)
	// BFS
	for d.Len() > 0 {
		emp := d.Remove(d.Front()).(*Employee)
		rst += emp.Importance
		for _, id := range emp.Subordinates {
			// 线性搜索查找
			for _, subEmp := range employees {
				if subEmp.Id == id {
					d.PushBack(subEmp)
				}
			}
		}
	}
	return rst
}


// dfs 解题： 官方题解，深度优先案例
func getImportance(employees []*Employee, id int) (total int) {
	mp := map[int]*Employee{}
	for _, employee := range employees {
		mp[employee.Id] = employee
	}

	var dfs func(int)
	dfs = func(id int) {
		employee := mp[id]
		total += employee.Importance
		for _, subId := range employee.Subordinates {
			dfs(subId)
		}
	}
	dfs(id)
	return
}
